package leetcode.solution;

/**
 * 你和你的朋友面前有一排石头堆，用一个数组 piles 表示，piles[i] 表示第 i 堆石子有多少个。
 * 你们轮流拿石头，一次拿一堆，但是只能拿走最左边或者最右边的石头堆。所有石头被拿完后，谁拥有的石头多，谁获胜。
 *
 * 石头的堆数可以是任意正整数，石头的总数也可以是任意正整数，这样就能打破先手必胜的局面了。
 * 比如有三堆石头 piles = [1, 100, 3]，先手不管拿 1 还是 3，能够决定胜负的 100 都会被后手拿走，后手会获胜。
 *
 * 假设两人都很聪明，请你设计一个算法，返回先手和后手的最后得分（石头总数）之差。
 * 比如上面那个例子，先手能获得 4 分，后手会获得 100 分，你的算法应该返回 -96。
 */
public class ShiTouDui {

    /**
     * 求解该题目，不应该从时间序列上考虑问题，而是应该把一排石头堆分解为由1到n-1个小石头堆组成的子序列，
     * 依次求解这些子序列各自先后手的最优解，那么最后就能求出n个石头堆先后手的最优解了
     */

    private static int score(int[] stones){
        int len = stones.length;
        // 石堆起始、结束位置、先手和后手最优解
        int[][][] dp = new int[len][len][2];

        // 先求石堆数n=1时, 然后一直到len
        for (int i = 0; i < len; i++){
            // 斜对角线求解
            for (int j = 0; j < len-i; j++){
                // 起点是j，终点是j+i
                if (i==0){
                    // 初始化第一条对角线, 先手为石堆数，后手为零
                    dp[j][j][0] = stones[j];
                }else {
                    // 最优先手数 即选左？右 分别对应两个子序列 选取最优后手+石堆数的那一个
                    // 最优后手数 则为选择子序列的最优先手
                    if (dp[j][j+i-1][1] + stones[j+i] > dp[j+1][j+i][1] + stones[j]){
                        dp[j][j+i][0] = dp[j][j+i-1][1] + stones[j+i];
                        dp[j][j+i][1] = dp[j][j+i-1][0];
                    }else {
                        dp[j][j+i][0] = dp[j+1][j+i][1] + stones[j];
                        dp[j][j+i][1] = dp[j+1][j+i][0];
                    }

                }
            }
        }
        return dp[0][len-1][0]-dp[0][len-1][1];
    }

    public static void main(String[] args){
        int[] a = new int[]{1,100,3};
        System.out.println(score(a));
    }

}
